`:top
The `!Linde–Buzo–Gray algorithm`! (named after its creators Yoseph Linde, Andrés Buzo and `F33f`_`[Robert M. Gray`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Robert_M._Gray]`_`f, who designed it in 1980)`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] is an `F33f`_`[iterative`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Iterative_method]`_`f `F33f`_`[vector quantization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Vector_quantization]`_`f algorithm to improve a small set of vectors (codebook) to represent a larger set of vectors (training set), such that it will be `F33f`_`[locally optimal`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Local_optimum]`_`f. It combines `F33f`_`[Lloyd's Algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lloyd's_Algorithm]`_`f with a splitting technique in which larger codebooks are built from smaller codebooks by splitting each code vector in two. The core idea of the algorithm is that by splitting the codebook such that all code vectors from the previous codebook are present, the new codebook must be as good as the previous one or better. `:cite-ref-gray1992-2-0[`F5bf`_`[2`#cite-note-gray1992-2]`_`f]
>>Contents
• `F0af`_`[Description`#description]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Description
The Linde–Buzo–Gray algorithm may be implemented as follows:
`B100`F9d9algorithm linde-buzo-gray is`f`b
`B100`F9d9 input: set of training vectors training, codebook to improve old-codebook`f`b
`B100`F9d9 output: codebook that is twice the size and better or as good as old-codebook`f`b
`B100`F9d9`f`b
`B100`F9d9 new-codebook ← {}`f`b
`B100`F9d9`f`b
`B100`F9d9 for each old-codevector in old-codebook do`f`b
`B100`F9d9 insert old-codevector into new-codebook`f`b
`B100`F9d9 insert old-codevector + 𝜖 into new-codebook where 𝜖 is a small vector`f`b
`B100`F9d9`f`b
`B100`F9d9 return lloyd(new-codebook, training)`f`b
`B100`F9d9algorithm lloyd is`f`b
`B100`F9d9 input: codebook to improve, set of training vectors training`f`b
`B100`F9d9 output: improved codebook`f`b
`B100`F9d9`f`b
`B100`F9d9 do`f`b
`B100`F9d9 previous-codebook ← codebook`f`b
`B100`F9d9`f`b
`B100`F9d9 clusters ← divide training into |codebook| clusters, where each cluster contains all vectors in training who are best represented by the corresponding vector in codebook`f`b
`B100`F9d9`f`b
`B100`F9d9 for each cluster cluster in clusters do`f`b
`B100`F9d9 the corresponding code vector in codebook ← the centroid of all training vectors in cluster`f`b
`B100`F9d9`f`b
`B100`F9d9 while difference in error representing training between codebook and previous-codebook > 𝜖`f`b
`B100`F9d9`f`b
`B100`F9d9 return codebook`f`b
`B100`F9d9`f`b
>>References
`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citereflindebuzogray1980`aLinde, Y.; Buzo, A.; Gray, R. (1980). "An Algorithm for Vector Quantizer Design". `*IEEE Transactions on Communications`*. `!28`! (1): 84–95. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/TCOM.1980.1094577. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0090-6778. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 18530691.
`:cite-note-gray1992-2`!2.`! `F0af`_`[↑`#cite-ref-gray1992-2-0]`_`f `:citerefgraygersho1992`aGray, R.; Gersho, A. (1992). `*Vector Quantization and Signal Compression`* (1 ed.). Springer. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/978-1-4615-3626-0. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-4613-6612-6.
`c`F0af`_`[↑ Back to top`#top]`_`f`a